Создайте программу, которая поможет герою произведения
Джерома К. Джерома “Трое в лодке, не считая собаки” Гарри быстрее выйти из Хэмптон-Кортского лабиринта.
Лабиринт на плане имеет вид прямоугольника, стороны которого направлены с
запада на восток или с севера на юг (насколько это возможно, учитывая
шарообразную форму Земли). Размеры лабиринта в ярдах (англ мера длины, примерно
91,44 см) вдоль параллели и меридиана выражено натуральными числами n и m
соответственно, а его общая площадь mn
не превышает 10000 (квадратных ярдов). Всю территорию лабиринта разделен на
квадраты с длиной стороны 1 ярд. Часть квадратов засажено кустами с колючками,
которые можно только обойти.
Вход. Первая строка содержит два натуральных числа m и n
– размеры лабиринта в ярдах. Следующие m
строк по n символов содержат схему
лабиринта, в которой символ “ ” (пробел)
означает свободный квадрат поверхности, символ “U” – квадрат с кустом, крестик (знак сложения) “+” – начальное расположение Гарри. Выходу из лабиринта соответствуют
элементы 1-ой и m-ой строки и 1-ого и
n-ого столбца, если они являются
пропуском или знаком сложения. Движение в лабиринте осуществляют в направлении
сторон света на свободный от кустов соседний квадрат. Движению на север юг,
запад или восток соответствует движение вверх, вниз, влево или вправо на один
символ на входной схеме.
Выход. Первая строка
должна содержать наименьшее количество шагов длины 1 ярд, которые должен
совершить Гарри чтобы выйти из лабиринта.
Вторая строка должна содержать описание такого кратчайшего
пути - шагов от первого до последнего, в котором буква n обозначает шаг на север (по-английски north), s – на юг (south), e –
на восток (east), w – на запад (west).
Если Гарри уже находится на выходе, то первая строка содержит
только число 0, а вторая строка пустая.
Если выйти из лабиринта невозможно (не будем обсуждать каким
образом в этом случае Гарри попал в соответствующее место лабиринта), то
единственная строка должна содержать только число -1.
|
Пример входа |
Пример выхода |
|
9 9 UUUUUUUUU U U UUUUUUU U U
+ U U U U U U U U U U U U U U U U U
U U UUUUUUUUU |
22 wwwsssswwnnnnnneeeeeee |
поиск в
ширину
Анализ
алгоритма
Запустим поиск в ширину из начального расположения Гарри. Для
каждой клетки вычислим минимальное количество шагов, за которое Гарри сможет в
нее попасть.
Реализация
алгоритма
Информацию о лабиринте будем хранить в массиве mas. В дальнейшем в mas[i][j]
будем вычислять наименьшее количество шагов, за которое Гарри сможет достичь
клетки (i, j). Очередь q хранит координаты клеток лабиринта и используется при
поиске в ширину. Переменные start и finish хранят начальное местоположение
Гарри и точку выхода из лабиринта. Клетку храним в классе Cell.
#define MAX 2100
int mas[MAX][MAX];
class Cell
{
public:
int x, y;
Cell(int x = 0, int y = 0)
: x(x), y(y) {}
};
queue<Cell> q;
Cell start, finish;
Поиск в ширину на лабиринте стартует из клетки (i, j).
Cell bfs(Cell Start)
{
int i = Start.x, j = Start.y;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
q.push(Start);
mas[i][j] = 0;
while(!q.empty())
{
i = q.front().x;
j = q.front().y; q.pop();
Если попали в клетку, находящуюся
на границе лабиринта, то она является выходом.
if ((i == 1) || (i == m) || (j == 1) || (j == n)) // exit found
return Cell(i,j);
Рассматриваем возможность
движения во все четыре стороны: вниз, вверх, влево, вправо. При передвижении в
клетку ее координаты заносим в очередь и пересчитываем соответствующую ячейку
массива кратчайших расстояний mas.
for(int k = 0; k <
4; k++)
if (mas[i + dx[k]][j + dy[k]] == -1)
{
q.push(Cell(i + dx[k],j + dy[k]));
mas[i +
dx[k]][j + dy[k]] = mas[i][j] + 1;
}
}
Если выход не найден – возвращаем
клетку с координатами (-1, -1).
return Cell(-1,-1);
}
Основная часть программы. Читаем
посимвольно лабиринт и заносим в массив mas информацию о нем. В start занесем координаты начальной точки
Гарри. Положим mas[i][j] = -1, если квадрат (i, j)
свободный. Если занятый, то положим mas[i][j] = -2.
scanf("%d %d\n",&m,&n);
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%c",&ch);
mas[i][j] = -1;
if (ch == '+')
start =
make_pair(i,j);
else
if (ch != ' ')
mas[i][j] = -2;
}
gets(s);
}
Запускаем из start поиск в ширину.
finish = bfs(start);
Если выход из лабиринта не
найден, то выводим -1.
if (finish.x == -1)
{
printf("-1\n");
return 0;
}
Выход из лабиринта найден.
Выводим искомое наименьшее количество шагов. Если оно равно 0, то завершаем
программу.
res = mas[finish.first][finish.second];
printf("%d\n",res);
if (res == 0) return 0;
В строке ans генерируем кратчайший путь, ведущий на выход из лабиринта.
Двигаемся из конечной точки до начального положения Гарри. Таким образом путь
получается в обратном порядке.
i = finish.x;
j = finish.y;
for(k = 0; k < res; k++)
{
if ((i > 1) && (mas[i-1][j] == mas[i][j] -
1))
i--,ans = ans + 's';
else
if ((i <
m) && (mas[i+1][j] == mas[i][j] - 1))
i++,ans = ans + 'n';
else
if ((j > 1) && (mas[i][j-1] == mas[i][j] -
1))
j--,ans = ans
+ 'e';
else
if ((j < n) && (mas[i][j+1] == mas[i][j] -
1))
j++,ans = ans + 'w';
}
Обращаем и выводим искомый путь.
reverse(ans.begin(),ans.end());
printf("%s\n",ans.c_str());